class Solution {
    vector<vector<string>> ans;
    vector<string> path;
    void backTracking(const string &s, int startIndex)
    {
        // 当切割到结尾获取结果集
        if(startIndex >= s.size())
        {
            ans.push_back(path);
            return;
        }

        for(int i = startIndex; i < s.size(); i++)
        {
            // 通过startIndex和i确定子串的范围
            // 在每个函数栈帧内，startIndex是不会变的，通过i的变化逐步截取不同的子串
            if(helper(s, startIndex, i))
                path.push_back(s.substr(startIndex, i - startIndex + 1));
            else
                continue;

            // 截取完当前字符，下一层递归就是下一个字符
            backTracking(s, i + 1);
            path.pop_back();    // 回溯的关键步骤
        }
    }

    bool helper(const string &s, int left, int right)
    {
        while(left < right)
        {
            if(s[left] != s[right])
                return false;
            left++;
            right--;
        }
        return true;
    }

public:
    vector<vector<string>> partition(string s) {
        backTracking(s, 0);
        return ans;
    }
};